1. Field of Invention
This invention relates to Electrical Computers and Data Processing Systems and more particularly to Applications to Design and Analysis of Electrical/Electronic Circuits.
2. Description of Prior Art
Usual way of projecting of the equipment that realizes the assigned algorithm consists of the following. (1) The (micro)processor and an appropriate programming language are chosen. (2) The computer program is written and debugged. (3) Read Only Memory that controls the program is hardwired by the debugged program.
As a rule, the computer instructions very little correspond to the algorithm operations. Hence, each block of the algorithm flowchart is realized by the set (subroutine) of computer instructions. The sequential order of the computer instructions' performance results in slowing down of the computer performance of the assigned algorithm. This is a disadvantage if algorithm has to work in a real-time scale, such as communications network control algorithms, error correcting code decoders' algorithms, rocket missiles pursuing algorithms. Thereafter, the hardware realization of the control algorithms performed as Moore or Mealy automatic machines, is implemented (see Automatic Logic Synthesis Techniques for Digital Systems, by M. D. Edwards, McGrow-Hilll, New York, 1992, ISBN 0-07-019417-3).
Digital circuit in a form of automatic machine consists of a set of logical elements, type AND, OR, and NOT (inverter), and binary memory elements. Digital circuit receives digital input signals, performs logic operations for the process of control, and directs its digital output signals to the executive parts of the computer system. Binary memory elements, that configured in the digital circuit, are connected to the outputs of logical elements. Each memory element creates a delay in one clock pulse. Therefore, memory element is implemented (that is, connected to the output of a certain logical element) only if it is needed for the correct realization of a control algorithm.
Implementation of digital circuits instead of programmable processors permits to reduce significantly the clock pulses number needed for the control algorithm realization. The speed of the control process increases by this in ten times or more without the change of the digital electronic technology.
The problem of control algorithms' realization by a digital circuit is solved in the book by M. D. Edwards and other known literature, by compiling and coding the state table of an automatic machine. (There are almost no differences between Moore and Mealy machine, see pg. 35 of the cited book). One of the most important problems in the finite state machines' implementation is the efficient binary encoding of the internal states of the machine (see pg. 38, 39). However, if i is the states' number, then "for i&lt;5 it is not feasible to try all the different assignments by enumerative methods in order to find the most economical combinatorial logic solution" (see pg. 131).
Several improved computerized state assignment algorithms included into the cited book: KISS and CREAM algorithms, MUSTANG technique, NOVA, K-MUSTARD and ASYL approaches. However, these algorithms also do not lead to an optimal solution, and the following recommendation included into the book. "For large finite state machines it can be more efficient to decompose a machine into an interconnection of two or more smaller submachines. The resulted submachines may subsequently be synthesized in the usual way" (pg. 132). This recommendation is caused by the lack of satisfactory solution of digital circuits' synthesis method.
U.S. Pat. No. 5,805,462 to Frank Poirot et al (1998, applicant: VLSI Technology, Inc., San Jose, Calif.) discloses automatic synthesis of integrated circuits employing Boolean decomposition. The problem of proper inclusion of memory elements for multistate algorithm realization is not solved in this invention.
The book The Behavior and Simplicity of Finite Moore Automata by Andras Adam, Budapest, 1996 is also devoted to digital circuits realizing the control algorithms. As the book by M. D. Edwards it describes the synthesis of digital circuits with the memory elements with the use of the internal states' table. This implementation is difficult for relatively complicated algorithms.
U.S. Pat. No. 4,703,435 to John A. Darringer et al. (1987, applicant IBM Corporation, Armonk, N.Y.) discloses an automated logic synthesis method. A register-transfer level flowchart specification in this method is translated straightforwardly into a single AND-OR logic implementation. Simplified AND-OR implementation is translated to a NAND or NOR representation, depending on the target technology, after logic implementation expands to elementary representation. The problem of the proper synthesis of automatic machine, realizing any finished algorithm, and including logic (of any type) and memory elements, was not stated in this invention.
U.S. Pat. No. 5,029,102 to Anthony D. Drumm et al (1991, applicant IBM Corporation, Armonk, N.Y.) discloses a logic synthesis method and system for a digital circuit, consisting of basic logic blocks. Method is improved to that of U.S. Pat. No. 4,703,435; some of the said blocks may not be primitive (logic) blocks. Method includes the novel technique for performing logic reduction on the individual expressions. However, the problem of the proper synthesis of automatic machine, for the finished algorithm realization, including logic and memory elements, was not stated in this invention.
U.S. Pat. No. 5,258,919 to Roy K. Yamanouchi et al (1993, applicant National Semiconductor Corporation, CA.) provides a structured integrated circuit design methodology, consisting of the following stages:
1) Describing a two-phase logic function using a highlevel behavioral description flowchart; PA0 2) Reducing trial and error in circuit layout implementation using novel chip planning techniques; PA0 3) Definition of signal types and the type of input signal that feeds the current function. A rigid set of rules is established for the signal types; PA0 4) Technical specification of the two-phase logic function is defined. A behavioral flowchart using defined symbols is created; PA0 5) An associated database of the Boolean equations for the parameters of the flowchart elements is created; PA0 6) Boolean equations are converted to a logic diagram by coded state assignment or by direct implementation; PA0 7) Resulted logic diagram is analyzed for speed utilizing a Figure of Merit technique; PA0 8) Circuit design is carried through to layout by CAD tools. PA0 (a) to provide a method for creation of a digital circuit which can work much faster, ten times or more, than a programmable processor using the same technology; PA0 (b) to provide the carrying-out of the digital circuit synthesis method directly according to the algorithm flowchart, during which the output of the realized algorithm operation is performed after and according to other conditional and unconditional operations pointed by the algorithm flowchart configuration; PA0 (c) to provide the said digital circuit synthesis method without the tedious usage of a not optimal representation of a said digital circuit by the state transition table; PA0 (d) to provide the convenience of the said method usage for the user, whose first task is to enter the algorithm according to the attached instructions; PA0 (e) to provide an automatic checking of the syntax of entered algorithm by the computer program included into the said method; PA0 (f) to provide an automatic work of the method and program after successful checking of the entered algorithm; PA0 (g) to provide full description of the created digital circuit realizing entered algorithm in two logical bases: AND-OR-NOT, and AND-NOT; PA0 (h) to provide automatic insertion of binary memory elements into the digital (logic) circuit only on those places, that are needed for the realization of entered algorithm.
The 6.sup.th stage among the indicated 8 stages is used to create a Mealy (or Moore) automatic machine and related to the proposed invention. The creation of automatic machine in U.S. Pat. No. 5,268,919 is based on sate assignment, creation of the state transition table, and output table, just as described in the book by M. D. Edwards, pg. 34.div.40. Improved algorithms for computerized state assignment, summarized in the book by M. D. Edwards from the previous literature, are not included in this patent. For these reasons the U.S. Pat. No. 5,268,919, as already cited book, cannot be used for the creation and optimization of the relatively complicated digital circuit.
U.S. Pat. No. 5,403,504 to Shin-Ichi Minato (1996, applicant Nippon Telegraph and Telephone Corporation, Tokyo, Japan) discloses a design system of a logic circuit, including a logic synthesis. Logic circuit includes a processing unit, and a set data processing unit. The set data processing unit includes a node table for the elements recording. The control unit of the logic synthesis and processing unit read data from the node table, assign a binary number to each element, and transfer to the data processing unit. The control unit of the data processing unit separates the set data ("0" from "1"), generates a 0-supressed binary decision diagram (BDD) of a logic function, and stores data to the node table. Intermediate nodes in BDD are eliminated. A subset, whose element number is smaller than that of the entire set is represented by a graph with a smaller number of nodes, than in a conventional BDD. Logic circuits, synthesized in this patent, are not related to automatic machines (Finite State Machines) and are not associated with the finished algorithms. The logic circuit examples shown on FIGS. 16, 19, 22 of this patent do not contain flip-flops (memory elements). Such a circuit can perform certain logic operations, but not an assigned algorithm. The problem of the synthesis of automatic machine, realizing an algorithm, including logic and memory elements, was not stated in this patent.
The article "Capture, Integration, and Analysis of Digital Systems Requirements with Conceptual Graphs" by Walling R. Cyre was published in "IEEE Trans. on Knowledge and Data Engineering," vol. 9, No. 1, 1997. Article focuses on the capture, integration, analysis of specifications (from English descriptions). A knowledge representation form, that supports natural language understanding, was selected in the article to be a common notation. This notation is a form of semantic networks called conceptual graphs. Conceptual graphs in this article are a useful tool for representing and combining knowledge or meaning. In the context of digital system requirements, general concept types include the device type, which include all the hardware elements. The type logic memory represents devices, that contain both logic for data manipulation and memory for storage of (type) values. This class of devices contains both processors and counters. Capture is the first step in the automatic evaluation and interpretation of requirements. Capture consists of entry and translation (of the types and values) of system requirements to conceptual graphs. The next direction of the future research is to analyze the preliminary design for cost and performance. Problem of the synthesis of automatic machine, realizing any algorithm (assigned by the user), where algorithm includes logic elements and flip-flops, is not considered in this article.